In data processing systems in which more than one source (competing sources) require access to a shared data bus, for example in local area networks (LANs), an arbitration scheme is required to control data traffic over the bus. Because only one source can gain access to the bus at a time, an arbitration protocol must be implemented to determine which of a plurality of sources requesting bus access is allowed to access the shared bus.
The arbitration scheme selected, however, generally involves a trade off between two competing factors, fairness and efficiency. A fair arbiter ensures that all competing sources, even those with relatively low priority, are not totally blocked from accessing the bus or denied access to the bus for unreasonably long periods of time. An arbiter which enables efficient use of the data bus may allow competing sources with higher priority to gain disproportionate access to the bus.
An example of an arbitration scheme which provides fair access to a shared data bus is round robin arbitration. In a round robin arbiter, competing sources are sequentially granted access to the bus. After a source has been granted bus access, it will not again be awarded bus access until all remaining access requests have been granted. The round robin arbiter enables each competing source to have temporary priority over other competing sources, thereby ensuring that all sources have an opportunity to access the bus. Another example of a fair arbitration protocol is first-come first-serve arbitration, in which competing sources are granted bus access in the same order in which they request bus access.
An arbitration scheme which ensures fair access to the shared data bus, however, may result in inefficient use of the bus. Often, it may be desirable for a high priority source to gain disproportionate access to the data bus. For example, certain sources may be faced with time constraints which require that they transmit data within a set period of time, and therefore efficient use of the data bus requires that these sources be granted access over lower priority sources.
Schemes such as round robin arbitration and first-come first-serve, although fair and relatively easy to implement, may result in unacceptable delays in granting access requests from these high priority sources. Accordingly, arbiters which favor efficiency over fairness often utilize a prioritization scheme in which sources are assigned relative priority values that are compared to determine which source gains access to the bus.
Priority schemes, however, generally suffer from the drawback that lower priority sources may be blocked from accessing the shared data bus for unacceptably long periods of time, particularly during periods of heavy data flow over the bus from higher priority sources. Furthermore, in an arbiter utilizing a prioritization scheme, a circuit having a large number of inputs is generally required to compare the priority values of all sources requesting access to the data bus.
As a consequence of the respective drawbacks of conventional fairness and priority based arbiters, choosing an appropriate arbitration protocol generally results in trade offs between fairness and efficiency.